package njupt.tree;

public class BBST<E> extends BST<E> {


    public BBST(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * 统一进行旋转
     * @param grand  代表子树的根节点
     * @param a
     * @param b
     * @param c
     * @param d
     * @param e
     * @param f
     * @param g
     */
    public void rotate(Node<E> grand,
                       Node<E> a,Node<E> b,Node<E> c,
                       Node<E> d,
                       Node<E> e,Node<E> f,Node<E> g){
        b.left=a;
        b.right=c;

        f.left=e;
        f.right=g;

        d.left=b;
        d.right=f;
        d.parent=grand.parent;

        if(grand.parent==null){
            root=d;
        }else if(grand.isLeftChild()){
            grand.parent.left=d;
        }else{
            grand.parent.right=d;
        }

        if(a!=null){
            a.parent=b;
        }
        if(c!=null){
            c.parent=b;
        }
        if(e!=null){
            e.parent=f;
        }
        if(g!=null){
            g.parent=f;
        }
        b.parent=d;
        f.parent=d;

    }


    /**
     * 左旋转
     * @param grand 传递的最低不平衡的那个节点
     */
    public void rotateLeft(Node<E> grand){
        Node<E> parent=grand.right;
        Node<E> child=parent.left;

        grand.right=child;

        parent.left=grand;

        afterRotate( grand,  parent,  child);
    }

    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        if (grand.parent == null) {
            root = parent;
        } else if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else {
            grand.parent.right = parent;
        }
        parent.parent = grand.parent;
        grand.parent = parent;
        //child可能为null
        if (child != null) {
            child.parent = grand;
        }
    }

    /**
     * 右旋转
     * @param grand 传递的最低不平衡的那个节点
     */
    public void rotateRight(Node<E> grand){
        Node<E> parent=grand.left;
        Node<E> child=parent.right;

        grand.left=child;

        parent.right=grand;
        afterRotate(grand, parent, child);
    }
}
